1304. Найти медиану

Медиана играет важную роль в мире статистики. По определению это число, которое делит массив на две равные части. В этой задаче Вам необходимо найти значение медианы для текущего набора целых чисел.

Например, рассмотрим последовательность {1, 3, 6, 2, 7}. Число 3 является медианой, так как по обе стороны от него находится в точности по два целых числа: {1, 2} и {6, 7}.

Если последовательность содержит четное количество чисел, как например {1, 3, 6, 2, 7, 8}, то одно число не может разбить массив на две равные части, поэтому в качестве медианы будем рассматривать среднее арифметическое центральных чисел {3, 6}. То есть медиана равна (3 + 6) / 2 = 4.5. В задаче Вам следует выводить только целую часть медианы, без дробной. То есть для данного примера ответом будет 4.

Вход. Состоит из набора целых чисел x ( 0 ≤ x < 2³¹), их количество не более 30000.

Выход. Для каждого входного числа в отдельной строке вывести медиану текущей последовательности. Для каждого значения медианы выводить только ее целую часть.

Пример входа	Пример выхода
1 3 4 60 70 50 2	1 2 3 3 4 27 4

РЕШЕНИЕ

поиск

Анализ алгоритма

Начиная с пустой последовательности, будем вставлять в нее текущие числа так, чтобы текущая последовательность оставалась отсортированной. Тогда ее медиана считается за константное время. Динамически поддерживаемую последовательность храним в структуре данных vector. Позицию очередного вставляемого элемента ищем при помощи функции lower_bound.

Время вставки в середину вектора пропорционально количеству элементов, стоящих за местом вставки. Поэтому указанный алгоритм в худшем случае будет работать за O(n²), где n – длина последовательности.

Реализация алгоритма

В динамическом массиве v типа vector будем хранить текущую считанную отсортированную по возрастанию последовательность. В переменной len храним длину текущей последовательности (количество считанных входных чисел).

vector<int> v;

int n, pos, len = 0;

Для каждого нового числа n при помощи функции lower_bound находим позицию pos, на которую можно вставить число n так, чтобы не нарушалось свойство отсортированности массива.

while(scanf("%d",&n) == 1)

{

len++;

pos = lower_bound(v.begin(),v.end(),n) - v.begin();

Вставляем число n в позицию pos.

v.insert(v.begin()+pos,n);

В зависимости от длины последовательности выводим значение ее медианы. Последняя равна v[len / 2], если количество чисел в последовательности нечетно и (v[len / 2] + v[len / 2 – 1]) / 2 иначе.

if (len & 1) printf("%d\n",v[len/2]);

else printf("%d\n",(v[len/2] + v[len/2-1])/2);

}

Реализация алгоритма – вставка в массив за O(n²)

#include <stdio.h>

#define MAX 30010

int m[MAX];

int i, val, len;

int main(void)

{

len = 0;

while(scanf("%d",&val) == 1)

{

m[len++] = val; i = len - 1;

while(i > 0 && m[i - 1] > val)

{

m[i] = m[i - 1];

i--;

}

m[i] = val;

if (len & 1) printf("%d\n",m[len/2]);

else printf("%d\n",(m[len/2] + m[len/2-1])/2);

}

return 0;

}